#ifndef _SDQUICK_SORT_H
#define _SDQUICK_SORT_H
#include <iostream>

namespace stdds {

	template <typename T>
		class QuickSort{
		public:
			enum { MAX_LEN=10 };
			T A[MAX_LEN];

			QuickSort(){}
			T& operator[](int pIndex){return A[pIndex];}

			void print(){
				for(int i=0;i<MAX_LEN;i++)
					std::cout<<A[i]<<" ";
				//std::cout<<"["<<i<<"-"<<A[i]<<"] ";
				std::cout<<std::endl;
			}

			int Partition(int p,int r) {
				T X = A[r];
				int i=p-1;
				for(int j=p;j<=r-1;j++)
				{
					if(A[j]<X)
					{
						i++;
						T E = A[i];
						A[i] = A[j];
						A[j] = E;
					}
					print();
				}
				i++;
				T E = A[i];
				A[i] = A[r];
				A[r] = E;
				print();

				std::cout<<"PIVOT : "<<i<<std::endl;
				return i;
			}

			int QSort(int p,int r) {
				if(p<r) {
					int q = Partition(p,r);
					QSort(p,q-1);
					QSort(q,r);
				}
			}
		};
}
#endif
